/**
 * Created by Zzz on 2017/7/11.
 * floyed  最短路径算法
 */
public class Floyed {

    private double[][] G;
    private int dim;
    private int[][] P;

    public Floyed(double[][] matrix) {
        this.G = matrix;
        dim = matrix.length;
        P=new int[dim][dim];
        init();
    }

    private void init(){
        for (int i = 0; i < dim; i++) {
            for (int j = 0; j < dim; j++) {
                if (G[i][j]<Double.MAX_VALUE){
                    P[i][j]=j;
                }else {
                    P[i][j]=-1;
                }
            }
        }
    }

    int p=0;
    public double[][] calcu() {
        System.out.println(0);
        for (int k = 0; k < dim; k++) {
            // 计算进度
            if (p!=(k*100/dim)){
                p=(k*100/dim);
                System.out.println(p);
            }

            for (int i = 0; i < dim; i++) {
                for (int j = 0; j < dim; j++) {
                    if (G[i][k] < Double.MAX_VALUE && G[k][j] < Double.MAX_VALUE && G[i][j] > G[i][k] + G[k][j]){
                        G[i][j] = G[i][k] + G[k][j];
                        P[i][j]=P[i][k];
                    }

                }
            }
        }
        return G;
    }

    public double distance(int i,int j){
        return G[i][j];
    }
}